def selection(arr):#选择
    n = len(arr)
    for i in range(n):#创建n个索引
        min_idx = i#初始化最小索引
        for j in range(i+1, n):#遍历剩余元素
            if arr[j] < arr[min_idx]:#如果当前元素小于最小索引元素，更新最小索引
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]#交换最小索引元素和当前元素
    return arr

#原地排序算法，时间复杂度O(n^2)
arr = [5, 2, 8, 3, 9, 1, 7, 4, 6]
print(selection(arr))